package com.wcj.test;

import com.wcj.linktable.ListNode;

/**
 * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * 数据范围： 10000≤n≤1000，−1000≤节点值≤1000
 * 要求：空间复杂度 O(1)，时间复杂度 O(n)
 *
 * 如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，
 * 所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
 */
public class 合并两个排序的链表 {

    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while (list1 != null && list2 != null){
            if (list1.val <= list2.val){
                tail.next = list1;
                list1 = list1.next;
            }else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = list1 != null ? list1 : list2;
        return head.next;
    }
}
